package com.lsa.letcode.the153.minInRotatedArrNoDupl;

public class Solution {
    public int findMin(int[] nums) {
    	if (nums.length == 0) {
    		throw new IllegalArgumentException();
    	}
    	else if (nums.length == 1) {
    		return nums[0];
    	}
    	
    	int idx = pivot(nums);
    	return nums[idx + 1];
    }
    
    private int pivot(int[] nums) {
    	int low = 0;
    	int len = nums.length;
		int high = len - 1;
    	while(low <= high) {
			int mid = (low + high) >> 1;
    		if (mid == 0) {
    			if (nums[0] > nums[1]) {
    				return 0;
    			}
    			else {
    				low = mid + 1;
    			}
    		}
    		else if (mid == len - 1) {
    			if (nums[len - 2] > nums[len - 1]) {
    				return len - 2;
    			}
    			else {
    				high = mid  - 1;
    			}
    		}
    		else {
    			if (nums[mid] > nums[mid + 1]) {
    				return mid;
    			}
    			else if (nums[mid - 1] > nums[mid]) {
    				return mid - 1;
    			}
    			else if (nums[mid] > nums[len - 1]){
    				low = mid + 1;
    			}
    			else {
    				high = mid - 1;
    			}
    		}
		}
		return -1;
	}
}